package Midium;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;

//528.按权重随机选择
public class Solution528 {
    int arr[];

    public Solution528(int[] w) {
        arr = new int[w.length];
        arr[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            arr[i] = arr[i - 1] + w[i];
        }
    }

    public int pickIndex() {
        // w:[5,1,2,3]
        // arr:[5,6,8,11]
        // rand = 0.4*11=4.4 --> 4 返回下标0 ，因为其在区间[0,5)里
        // rand = 0.7*11=7.7 --> 7 返回下标2 ，因为其在区间[6,8)里
        if(arr[arr.length-1]==1)
            return 0;
        Random random = new Random();
//        int rand = (int) ((Math.random() * (arr[arr.length - 1] - 1)));
        int rand = random.nextInt(arr[arr.length-1]); //rand生成的是左闭右开的区间的随机数


        // 在arr里寻找rand，返回其对应区间的下标的左边
        // 二分法查找
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (arr[mid] == rand) {
                // 特别注意：相等的时候，是算到下一个区间里的
                return mid+1;
            } else if (arr[mid] > rand) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return i;
    }

    //经测试发现，输出下标0的次数过多
    public static void main(String[] args) {
        int arr[] = new int[]{3, 14, 1, 7};
        Solution528 s = new Solution528(arr);

        for (int i = 0; i < 50; i++) {
            int result = s.pickIndex();
            System.out.print(result + " ");
        }

    }
}
